# 01 背包求组合数量
class Solution:
    @staticmethod
    def findTargetSumWays(nums: list[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和

        # 一维 容量
        dp = [0 for _ in range(target_sum+1)]

        # 初始化状态
        dp[0] = 1
        # 动态规划过程
        for num in nums:
            for j in range(target_sum,-1,-1):
                if j-num >= 0:
                    dp[j] += dp[j-num]
        return dp[target_sum]  # 返回达到目标和的方案数

        
if __name__ == "__main__":
    s = Solution()
    print(s.findTargetSumWays(nums=[0,],target=0))